package realQuestion.youdeke;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Main2 {

    List<String> ans=  new ArrayList<String>();
    List<String> sb=  new ArrayList<String>();
    public String[] wordDiv (String s, String[] dic) {
        // write code here
        HashSet<String> total = new HashSet<>();
        for (String a:dic) {
            total.add(a);
        }
        backTracking(0,s,total);
        String[] res = new String[ans.size()];
        ans.toArray(res);
        return  res;
    }

    public   void  backTracking(int startIndex,String s,HashSet<String>total){
        if (startIndex>=s.length()){
            StringBuffer stringBuffer = new StringBuffer();
            for (int i = 0; i < sb.size()-1; i++) {
                stringBuffer.append(sb.get(i));
            }
            ans.add(stringBuffer.toString());
            return;
        }
        for (int i = startIndex; i <s.length() ; i++) {
            if (judge(s,startIndex,i,total)){
                sb.add(s.substring(startIndex,i+1));
                sb.add(" ");
            }else {
                continue;
            }
            backTracking(i+1, s, total);
            sb.remove(sb.size()-1);
            sb.remove(sb.size()-1);
        }

    }


    public boolean  judge(String s,int startIndex,int end,HashSet<String>total){
        if (total.contains(s.substring(startIndex,end+1))){
            return  true;
        }else {
            return  false;
        }
    }

    public static void main(String[] args) {
        Main2 main2 = new Main2();
        String[]  arr=new String[]{"now","coder","no","wcoder"};
        String[] nowcoders = main2.wordDiv("nowcoder", arr);
        for (String a:
             nowcoders) {
            System.out.println(a);

        }


    }



}
